#include "GL/glut.h"
#include "stdio.h"
#include "math.h"

void MidpointLine(int x0, int y0, int x1, int y1)    //中点画线法无法解决斜率接近正无穷的情况
{
	if ((x0 != x1) && (y0 != y1))
	{
		int a, b, delta1, delta2, d, x, y;
		float k = (float)(y1 - y0) / (float)(x1 - x0);
		if (k >= 0 && k <= 1)
		{
			a = y0 - y1;
			b = x1 - x0;
			d = 2 * a + b;
			delta1 = 2 * a;
			delta2 = 2 * (a + b);
			x = x0;
			y = y0;
			glVertex2i(x, y);
			while (x < x1)
			{
				if (d < 0)
				{
					x++;
					y++;
					d += delta2;
				}
				else
				{
					x++;
					d += delta1;
				}
				glVertex2i(x, y);
			}
		}
		else if (k > 1)
		{
			a = y0 - y1;
			b = x1 - x0;
			d = a + 2 * b;
			delta1 = 2 * (a + b);
			delta2 = 2 * b;
			x = x0;
			y = y0;
			glVertex2i(x, y);
			while (y < y1)
			{
				if (d < 0)
				{
					y++;
					d += delta2;
				}
				else
				{
					y++;
					x++;
					d += delta1;
				}
				glVertex2i(x, y);
			}
		}
		else if (k >= -1 && k <= 0)
		{
			a = y0 - y1;
			b = x1 - x0;
			d = 2 * a - b;
			delta1 = 2 * a - 2 * b;
			delta2 = 2 * a;
			x = x0;
			y = y0;
			glVertex2i(x, y);
			while (x < x1)
			{
				if (d < 0)
				{
					x++;
					d += delta2;
				}
				else
				{
					x++;
					y--;
					d += delta1;
				}
				glVertex2i(x, y);
			}
		}
		else//k<-1
		{
			a = y0 - y1;
			b = x1 - x0;
			d = a - 2 * b;
			delta1 = -2 * b;
			delta2 = 2 * (a - b);
			x = x0;
			y = y0;
			glVertex2i(x, y);
			while (y > y1)
			{
				if (d < 0)
				{
					x++;
					y--;
					d += delta2;
				}
				else
				{
					y--;
					d += delta1;
				}
				glVertex2i(x, y);
			}
		}
	}
	else//横/竖向直线
	{
		int min, d;
		if (x0 == x1)
		{
			int x = x0, y;
			y = (y0 <= y1) ? y0 : y1;
			d = fabs((double)(y0 - y1));
			while (d >= 0)
			{
				glVertex2i(x, y);
				y++;
				d--;
			}
		}
		if (y0 == y1)
		{
			int x, y = y0;
			x = (x0 <= x1) ? x0 : x1;
			d = fabs((double)(x0 - x1));
			while (d >= 0)
			{
				glVertex2i(x, y);
				x++;
				d--;
			}
		}
	}
}

void lineSegment()
{
	glClear(GL_COLOR_BUFFER_BIT);
	glColor3f(0.0, 0.0, 0.0);
	glBegin(GL_POINTS);
	MidpointLine(50, 450, 300, 450);
	MidpointLine(75, 425, 275, 425);
	MidpointLine(300, 450, 300, 350);
	MidpointLine(275, 425, 275, 375);
	MidpointLine(75, 425, 75, 375);
	MidpointLine(75, 375, 275, 375);
	//MidpointLine(75, 350, 300, 350);
	MidpointLine(75, 350, 175, 350);
	MidpointLine(205, 350, 300, 350);
	MidpointLine(50, 450, 50, 100);
	MidpointLine(75, 350, 75, 165);

	MidpointLine(50, 100, 100, 150);
	MidpointLine(75, 165, 100, 190);
	MidpointLine(100, 150, 100, 190);

	//MidpointLine(140, 250, 275, 250);
	MidpointLine(140, 250, 195, 250);
	MidpointLine(225, 250, 275, 250);
	//MidpointLine(140, 275, 275, 275);
	MidpointLine(140, 275, 190, 275);
	MidpointLine(220, 275, 275, 275);
	MidpointLine(140, 250, 140, 275);
	MidpointLine(275, 250, 275, 275);

	//MidpointLine(175, 350, 225, 100);
	MidpointLine(175, 350, 190, 275);
	MidpointLine(195, 250, 225, 100);
	//MidpointLine(205, 350, 240, 170);
	MidpointLine(205, 350, 220, 275);
	MidpointLine(225, 250, 241, 170);

	MidpointLine(225, 100, 265, 140);
	MidpointLine(241, 170, 265, 194);

	MidpointLine(265, 140, 265, 194);

	glEnd();
	glFlush();
}

const int POINTNUM = 22;      //多边形点数.

/******定义结构体用于活性边表AET和新边表NET***********************************/
typedef struct XET
{
	float x;
	float dx, ymax;
	XET* next;
}AET, NET;

/******定义点结构体point******************************************************/
struct point
{
	float x;
	float y;
}
polypoint[POINTNUM] = { 50,450,50,100,100,150,100,190,75,165,75,350,175,350,190,275,140,275,140,250,195,250,225,100,265,140,265,194,241,170,225,250,275,250,275,275,220,275,205,350,300,350,300,450 };//多边形顶点

point rectangle[4] = { 75, 425,275, 425,275, 375,75, 375 };
void PolyScan()
{
	/******计算最高点的y坐标(扫描到此结束)****************************************/
	int MaxY = 0;
	int i;
	for (i = 0;i < POINTNUM;i++)
		if (polypoint[i].y > MaxY)
			MaxY = polypoint[i].y;

	/*******初始化AET表***********************************************************/
	AET *pAET = new AET;
	pAET->next = NULL;

	/******初始化NET表************************************************************/
	NET *pNET[1024];
	for (i = 0;i <= MaxY;i++)
	{
		pNET[i] = new NET;
		pNET[i]->next = NULL;
	}
	glClear(GL_COLOR_BUFFER_BIT);        //赋值的窗口显示.
	glColor3f(0.0, 0.0, 0.0);             //设置直线的颜色黑色
	glBegin(GL_POINTS);
	/******扫描并建立NET表*********************************************************/
	for (i = 0;i <= MaxY;i++)
	{
		for (int j = 0;j < POINTNUM;j++)
			if (polypoint[j].y == i)
			{  //一个点跟前面的一个点形成一条线段，跟后面的点也形成线段
				if (polypoint[(j - 1 + POINTNUM) % POINTNUM].y > polypoint[j].y)
				{
					NET *p = new NET;
					p->x = polypoint[j].x;
					p->ymax = polypoint[(j - 1 + POINTNUM) % POINTNUM].y;
					p->dx = (polypoint[(j - 1 + POINTNUM) % POINTNUM].x - polypoint[j].x) / (polypoint[(j - 1 + POINTNUM) % POINTNUM].y - polypoint[j].y);
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
				if (polypoint[(j + 1 + POINTNUM) % POINTNUM].y > polypoint[j].y)
				{
					NET *p = new NET;
					p->x = polypoint[j].x;
					p->ymax = polypoint[(j + 1 + POINTNUM) % POINTNUM].y;
					p->dx = (polypoint[(j + 1 + POINTNUM) % POINTNUM].x - polypoint[j].x) / (polypoint[(j + 1 + POINTNUM) % POINTNUM].y - polypoint[j].y);
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
			}
	}
	/******建立并更新活性边表AET*****************************************************/
	for (i = 0;i <= MaxY;i++)
	{
		//计算新的交点x,更新AET
		NET *p = pAET->next;
		while (p)
		{
			p->x = p->x + p->dx;
			p = p->next;
		}
		//更新后新AET先排序*************************************************************/
		   //断表排序,不再开辟空间
		AET *tq = pAET;
		p = pAET->next;
		tq->next = NULL;
		while (p)
		{
			while (tq->next && p->x >= tq->next->x)
				tq = tq->next;
			NET *s = p->next;
			p->next = tq->next;
			tq->next = p;
			p = s;
			tq = pAET;
		}
		//(改进算法)先从AET表中删除ymax==i的结点****************************************/
		AET *q = pAET;
		p = q->next;
		while (p)
		{
			if (p->ymax == i)
			{
				q->next = p->next;
				delete p;
				p = q->next;
			}
			else
			{
				q = q->next;
				p = q->next;
			}
		}
		//将NET中的新点加入AET,并用插入法按X值递增排序**********************************/
		p = pNET[i]->next;
		q = pAET;
		while (p)
		{
			while (q->next && p->x >= q->next->x)
				q = q->next;
			NET *s = p->next;
			p->next = q->next;
			q->next = p;
			p = s;
			q = pAET;
		}
		/******配对填充颜色***************************************************************/

		p = pAET->next;
		while (p && p->next)
		{
			for (float j = p->x;j <= p->next->x;j++)
				glVertex2i(static_cast<int>(j), i);
			p = p->next->next;//考虑端点情况
		}
	}
	glEnd();
	glFlush();

	glColor3f(1.0, 1.0, 1.0);               //设置颜色为白色
	glBegin(GL_POLYGON);					//绘制模式为凸多边形
	glClear(GL_COLOR_BUFFER_BIT);   //清空颜色缓冲池
	for (i = 0;i < 4;i++)
	{
		glVertex2f(rectangle[i].x, rectangle[i].y);
	}          //指定绘制的四个顶点

	glEnd();
	glFlush();
}

void translation()
{
	for (int i = 0;i < POINTNUM;i++)
	{
		polypoint[i].x = polypoint[i].x + 100;
	}
	for (int i = 0;i < 4;i++)
	{
		rectangle[i].x = rectangle[i].x + 100;
	}
}

void reflect()
{
	float temp;
	for (int i = 0;i < POINTNUM;i++)
	{
		temp = polypoint[i].x;
		polypoint[i].x = polypoint[i].y;
		polypoint[i].y = temp;
	}
	for (int i = 0;i < 4;i++)
	{
		temp = rectangle[i].x;
		rectangle[i].x = rectangle[i].y;
		rectangle[i].y = temp;
	}
}
int main(int argc, char * argv[])
{
	glutInit(&argc, argv);//对GLUT进行初始化
	glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示方式
	glutInitWindowPosition(100, 100);//设置窗口在屏幕中的位置
	glutInitWindowSize(500, 500);//设置窗口的大小
	glutCreateWindow("中点划线法");//根据前面设置的信息创建窗口。参数将被作为窗口的标题
	glClearColor(1.0, 1.0, 1.0, 0.0);//背景颜色
	glMatrixMode(GL_PROJECTION);
	gluOrtho2D(0.0, 500.0, 0.0, 500.0);
	//glutDisplayFunc(lineSegment);//设置一个函数，当需要进行画图时，这个函数就会被调用

	translation();//平移
	reflect();//反射
	glutDisplayFunc(PolyScan);        //图形的定义传递给window.

	glutMainLoop();//进行一个消息循环
	return 0;
}